/*
 * Ex:			
 * File name:   iNode_fs.h
 *
 *  Created on: May 21, 2012
 *      Author: ayash
 *
 *
 * Descriptor:
 *
 */

#ifndef INODE_FS_H_
#define INODE_FS_H_

#include "FileSystem.h"
#include <cassert>
#include <math.h>

typedef struct
{
	uint size_residue;
	ulong num_used_blocks;

} level_residue_t;


class iNode_fs: public FileSystem
{

public:

	iNode_fs(unsigned int block_size,
			 unsigned int pointer_size,
	  	     unsigned int maximal_size,
	  	     result_t &result):
	  	    	FileSystem(block_size, pointer_size, maximal_size),
	  	    	_num_direct_pointers( block_size / pointer_size ),
	  	    	_max_level(0)
	{

		uint num_pointers_in_block = block_size / pointer_size;
		ulong current_level_max_size = _num_direct_pointers * block_size;
		ulong max_size_supported = current_level_max_size;


		result = OPERATION_SUCCESS;

		while ( max_size_supported < maximal_size )
		{
			-- _num_direct_pointers;

			if ( ! _num_direct_pointers )
			{
				// there are no direct pointers
				result = ERROR_MAX_FILE_SIZE_NOT_SUPPORTED;
				break;
			}

			++_max_level; // mark that we need a pointer of higher level

			// subtract the size of removed direct pointer
			max_size_supported -= block_size;

			// add the new size to the total
			max_size_supported += current_level_max_size;

			/*
			 * the size that the new pointer adding equal:
			 * 			# pointers in block * the supported size of the previous level
			 */
			current_level_max_size *= num_pointers_in_block;
		}

		// calculate sizes that will be used for each file's resources
		ulong max_num_blocks_level = 0;
		for ( uint i = 0; i < _max_level; ++i )
		{
			_max_size_level.push_back( pow( num_pointers_in_block , i ) * _block_size);
			max_num_blocks_level +=  pow( num_pointers_in_block , i );
			_max_num_blocks_level.push_back(max_num_blocks_level);
		}


		DBG_PRINT("iNode FS: # pointers: %u \t # direct: %u \t max level: %u\n",
				  _block_size / _pointer_size,
				  _num_direct_pointers,
				  _max_level);
	}


	~iNode_fs() {}

	result_t calc_file_perf ( uint file_size, file_perf_t & file_perf )
	{
		uint num_pointers_in_block;
		ulong current_level_max_size;
		ulong current_level_max_needed_block;
		uint i;

		assert( file_size );

		file_perf.avg_block_access = 0;
		file_perf.num_block_used = 1;

		uint tmp_size = file_size;


		ulong sum_access = 0; // the sum of access blocks
		uint residue; // the number of bytes in the current block

		// subtract the size of blocks that can be accessed through direct pointers
		for( i = 0; i < _num_direct_pointers; ++i )
		{
			residue = ( tmp_size > _block_size )? _block_size : tmp_size;

			sum_access += residue * 2; // for direct pointer we need to access 2 blocks
			++ file_perf.num_block_used;

			tmp_size -= residue;

			if ( ! tmp_size )
			{
				// all the file can be accessed through direct pointers
				goto end;

			}
		}


		num_pointers_in_block = _block_size / _pointer_size;

		// max size of first level
		current_level_max_size = num_pointers_in_block * _block_size;

		/*
		 * first level needs one block for the pointers
		 * and has num_pointers_in_block of direct blocks
		 */
		current_level_max_needed_block = 1 + num_pointers_in_block;

		for ( i = 1; i <= _max_level; ++i )
		{
			if ( tmp_size >= current_level_max_size )
			{
				/*
				 * for level i we need to access (i + 2) blocks in order to get the byte
				 * (header -> i levels of pointers -> the actual block)
				 */
				sum_access += current_level_max_size * ( i + 2 );

				tmp_size -= current_level_max_size;

				current_level_max_size *= num_pointers_in_block;

				file_perf.num_block_used += current_level_max_needed_block;

				current_level_max_needed_block =
						(current_level_max_needed_block * num_pointers_in_block) + 1;

				assert( ! (i == _max_level && ! tmp_size) );
			}
			else
			{
				// the current level maximal supported size is more than the residue
				break;
			}
		}

		if ( tmp_size )
		{
			// we still have bytes that weren't calculated

			/*
			 * calculate the resources that are needed from the highest level
			 * that are being used
			 */


			// all the rest bytes are accessed by the sum number of pointers
			sum_access += tmp_size * ( i + 2 );

			level_residue_t level_residue = accurate_num_block_used( i, tmp_size );

			assert( ! level_residue.size_residue );

			file_perf.num_block_used += level_residue.num_used_blocks;

		}

end:
		file_perf.avg_block_access = ((double) sum_access) / file_size ;

		return OPERATION_SUCCESS;
	}



private:

	level_residue_t accurate_num_block_used(uint level, uint size)
	{
		level_residue_t level_residue;
		level_residue_t tmp_residue;

		level_residue.num_used_blocks = 1; // we need block for the pointers

		if ( ! level )
		{
			// direct block
			level_residue.size_residue = (size > _block_size) ? (size - _block_size) : 0;

			return level_residue;
		}


		uint num_pointers_in_block = _block_size / _pointer_size;
		uint tmp_size = size;


		ulong max_size_lower_level = _max_size_level.at(level - 1);

		ulong max_num_blocks_lower_level = _max_num_blocks_level.at( level -1 );

		for( uint i = 0; i < num_pointers_in_block; ++i )
		{
			if ( tmp_size >= max_size_lower_level )
			{
				tmp_size -= max_size_lower_level;
				level_residue.num_used_blocks += max_num_blocks_lower_level;
			}
			else
			{
				tmp_residue = accurate_num_block_used(level - 1, tmp_size);

				tmp_size = tmp_residue.size_residue;
				level_residue.num_used_blocks += tmp_residue.num_used_blocks;

			}

			if ( ! tmp_size )
			{
				break;
			}
		}

		level_residue.size_residue = tmp_size;
		return level_residue;
	}



	uint _num_direct_pointers;
	uint _max_level;

	vector<ulong> _max_size_level;
	vector<ulong> _max_num_blocks_level;

};


#endif /* INODE_FS_H_ */
